from typing import List


# 17. 电话号码的字母组合
# 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
def letterCombinations(digits: str) -> List[str]:
    digit_map = {"2": "abc", "3": "def",
                 "4": "ghi", "5": "jkl", "6": "mno",
                 "7": "pqrs", "8": "tuv", "9": "wxyz"}

    re = list()
    max_index = len(digits) - 1

    def combination(origin: str, current_index: int, next_index: int, strList: List[str]):
        '''
        使用回溯的方法
        :param origin: 初始的字符串
        :param current_index: 当前处理的数字下标
        :param next_index: 下一个要处理的数字下标
        :param strList: 最终的结果储存到这个List里面
        :return:
        '''

        # 考虑特殊情况，传的是空字符串
        if current_index > max_index:
            return

        # 当前遍历的数字
        current_num_char = digits[current_index]
        current_num_char_to_str = digit_map.get(current_num_char)

        # 遍历当前的数字，对应的字符串
        for current_str_index in range(len(current_num_char_to_str)):
            # 后面没有数字
            if current_index == max_index:
                strList.append(origin + current_num_char_to_str[current_str_index])
            # 后面还有数字
            else:
                combination(origin + current_num_char_to_str[current_str_index], next_index, next_index + 1, strList)

    # 方法开始调用
    combination('', 0, 1, re)

    return re


digits_1 = "23"
result = letterCombinations(digits_1)
print(f"result:{result}")

digits_1 = ""
result = letterCombinations(digits_1)
print(f"result:{result}")

digits_1 = "2"
result = letterCombinations(digits_1)
print(f"result:{result}")
